package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-07-26 10:33
 * @description: Functions of this class is 求二叉树的最大子树和
 **/
public class 二叉树的最大子树和 {
    private static int maxSum = Integer.MIN_VALUE;

    public static class TNode {
        int val;
        TNode left, right;
    }

    private static TNode createTree() {
        TNode root = new TNode();

        TNode node1 = new TNode();
        TNode node2 = new TNode();
        TNode node3 = new TNode();
        TNode node4 = new TNode();
        /*
                6
             3    -7
          -1  9
         */
        root.val = 6;
        node1.val = 3;
        node2.val = -7;
        node3.val = -1;
        node4.val = 9;
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node2.right = node3.left = node3.right = node4.left = node4.right = null;
        return root;
    }

    private static Integer findMaxTree(TNode T, TNode maxTree) {
        if (T == null) {
            return 0;
        }
        int leftMax = findMaxTree(T.left, maxTree);
        int rightMax = findMaxTree(T.right, maxTree);
        int sum = leftMax + rightMax + T.val;
        if (sum > maxSum) {
            maxSum = sum;
            maxTree.val = T.val;
        }
        return sum;
    }

    public static void main(String args[]) {
        TNode T = createTree();
        TNode maxTree = new TNode();
        findMaxTree(T, maxTree);
        System.out.println("其最大子树和为：" +maxSum +"\n最大子树的根节点为："+maxTree.val);
    }
}